Về tên gọi chính thức (núi Nhạn), có ba giả thuyết. Một là, do núi có hình thế như con chim nhạn xòe đôi cánh, với phần đầu là chỗ giao nhau giữa Quốc lộ 1A và sông Chùa, cổ thon nhỏ lại rồi phình to ra như đôi cánh chim ở phần đường Tản Đà. Hai là, vì ngày xưa núi này có loài nhạn đến ở. Và ba là, vì ngôi tháp cổ trên núi nhìn từ xa giống như con chim nhạn.

Về quá trình hình thành núi Nhạn, truyền thuyết kể rằng, thuở xa xưa đất Tuy Hòa là một vùng đầm lầy trũng thấp, là nơi cư trú của nhiều loài thủy sinh và thú dữ. Để có chỗ cho dân sinh sống, và cũng để bảo vệ người dân, một ngày kia Trời sai một người khổng lồ xuống gánh đá lấp đầy những vùng trũng, hình thành cả một cánh đồng Tuy Hòa bây giờ. Tuy nhiên, đến khi đổ đá lấn biển, vì muốn sớm về trời, người khổng lồ kia đã gánh nặng gấp hai ba lần. Do đó, trong một lần gánh, chiếc đòn gánh bỗng gãy đôi vì quá nặng, làm rơi xuống cả hai thúng đá, và đó chính là hai cụm núi: núi Nhạn và núi Chóp Chài.